/*
 * File: BFSProcessor.java 
 *  
 * Created on 15.10.2004
 */
package de.graph.mapper.impl;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

import de.graph.common.Edge;
import de.graph.common.Graph;
import de.graph.common.Vertex;
import de.graph.common.impl.GraphFactory;
import de.graph.common.impl.GraphFactory.GraphType;

/**
 * Der Graph wird mittels Breitensuche durchsucht.
 * 
 * @author dlade
 */
public class BFSMapperImpl extends GraphMapperImpl {

    protected BFSMapperImpl() {
    }

    public Graph map(Graph graph) {
        return map(graph.getVertices());
    }
    
    public Graph map(Vertex ...startVertices) {
        Graph newGraph = GraphFactory.create(GraphType.DIRECTED);
        if (startVertices == null) {
            return newGraph;
        }
        
        return map(Arrays.asList(startVertices));
    }

    public Graph map(Iterable<Vertex> startVertices) {
        Graph newGraph = GraphFactory.create(GraphType.DIRECTED);
        if (startVertices == null) {
            return newGraph;
        }
        
        int depth = 0;
        Deque<Vertex> vertexQueue = new ArrayDeque<Vertex>();

        Map<Vertex, Vertex> vertexMap = new HashMap<Vertex, Vertex>();

        for (Vertex startVertex : startVertices) {
            Vertex newSource = copyVertex(newGraph, startVertex, depth);

            vertexQueue.offerLast(startVertex);
            vertexMap.put(startVertex, newSource);
        }
        
        while (!vertexQueue.isEmpty()) {
            Vertex oldSource = vertexQueue.pollFirst();
            Vertex newSource = vertexMap.get(oldSource);
            depth = newSource.getProperty("depth");

            for (Edge oldEdge : oldSource.getOutEdges()) {
                Vertex oldTarget = oldEdge.getTargetVertex();
                Vertex newTarget = vertexMap.get(oldTarget);

                if (newTarget == null) {
                    newTarget = copyVertex(newGraph, oldTarget, depth + 1);

                    newGraph.createEdge(newSource, newTarget);
                    
                    vertexQueue.offerLast(oldTarget);

                    vertexMap.put(oldTarget, newTarget);
                }
            }
        }

        return newGraph;
    }
    
    private Vertex copyVertex(Graph newGraph, Vertex oldVertex, int depth) {

        Vertex newVertex = copyVertex(newGraph, oldVertex);
        newVertex.setProperty("depth", depth);

        return newVertex;
    }
}
